import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 * <p>
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * [1, 7],
 * [1, 2, 5],
 * [2, 6],
 * [1, 1, 6]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.combinationSum2(new int[]{1, 1, 2, 2, 4, 4, 4, 5, 5}, 10);
        System.out.println(lists.size());
    }

    /**
     * 记录数组频率
     **/
    List<int[]> freq = new ArrayList<int[]>();
    /**
     * 记录最后结果
     **/
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    /**
     * 记录暂时的结果
     **/
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    /**
     * 从0开始进入递归，直接递归下去，增加回溯
     *
     * @param pos
     * @param rest
     */
    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }
        // 从1开始进入递归
        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        // 最多需要几个当前值
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        // 处理完成之后回溯当前修改
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }


    /**
     * 从头开始用动态规划去算
     *
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum21(int[] candidates, int target) {
        // 先排序
        Arrays.sort(candidates);
        // 判断是不是需要处理
        if (candidates[0] > target) {
            return new ArrayList<>();
        }
        // 开始处理
        Set[] dp = new HashSet[target + 1];
        Set tmp, used;
        String tmpString;
        int min = candidates[0], max = candidates[0], add = candidates[0];
        tmp = new HashSet();
        tmp.add(candidates[0] + "");
        dp[candidates[0]] = tmp;
        for (int i = 1; i < candidates.length; i++) {
            if (candidates[i] == target) {
                // 如果最小值加当前值多余目标，加入后跳出
                if (dp[target] == null) {
                    dp[target] = new HashSet<String>();
                }
                dp[target].add(candidates[i] + "");
                break;
            } else if (candidates[i] > target) {
                // 如果最小值加当前值大于了目标，则跳出
                break;
            }
            used = new HashSet<String>();
            for (int j = min; j <= max && j <= target - 1; j++) {
                // 在最小值和最大值中每个都加上当前值
                if (null != dp[j]) {
                    add = j + candidates[i];
                    if (add <= target) {
                        tmp = dp[j];
                        if (dp[add] == null) {
                            dp[add] = new HashSet<String>();
                        }
                        // 遍历tmp
                        for (Object s : tmp) {
                            if (!used.contains(s)) {
                                tmpString = s + "," + candidates[i];
                                if (!dp[add].contains(tmpString)) {
                                    used.add(tmpString);
                                    dp[add].add(tmpString);
                                }
                            }
                        }
                    }
                }
            }
            // 把自身加入
            if (dp[candidates[i]] == null) {
                dp[candidates[i]] = new HashSet<String>();
            }
            dp[candidates[i]].add(candidates[i] + "");
            max = add;
        }

        // 处理dp[target]
        List<List<Integer>> result = new ArrayList<>();
        tmp = dp[target];
        if (null != tmp) {
            List tmpList;
            String[] tmpArray;
            for (Object s : tmp) {
                tmpArray = ((String) s).split(",");
                tmpList = new ArrayList();
                for (String s1 : tmpArray) {
                    tmpList.add(Integer.valueOf(s1));
                }
                result.add(tmpList);
            }
        }
        return result;
    }

    /**
     * 从尾部找
     *
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum22(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        // 先排序
        Arrays.sort(candidates);
        int head = -1, tail = candidates.length - 1;
        int[] sum = new int[candidates.length];
        sum[0] = candidates[0];
        for (int i = 1; i < candidates.length; i++) {
            if (head == -1) {
                sum[i] = sum[i - 1] + candidates[i];
                // 找到待匹配的头
                if (sum[i] == target) {
                    result.add(Arrays.stream(Arrays.copyOf(candidates, i)).boxed().collect(Collectors.toList()));
                    head = i + 1;
                } else if (sum[i] > target) {
                    head = i;
                }
            }
            // 找到待匹配的尾
            if (candidates[i] == target) {
                result.add(Collections.singletonList(i));
                tail = i - 1;
                break;
            } else if (candidates[i] > target) {
                tail = i - 1;
                break;
            }
        }
        // 从tail开始，到head结束
        Arrays[][] arrays = new Arrays[candidates.length][target];
        for (; head <= tail; tail--) {

        }
        return result;
    }


}